By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 38, Issue 2, pp. vii-752

Please Note: Electronic articles are available well in advance of the printed articles.

Special Issue: Dedicated to the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2005)
What Article options are available ?   View Cart   

Special Issue Dedicated to the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2005)

Ronald Fagin, Anupam Gupta, Ravi Kumar, and Ryan O'Donnell

p. vii

BibTeX  Abstract Full Text:  PDF

An $O(\logn \log\logn)$ Space Algorithm for Undirected st-Connectivity

Vladimir Trifonov

pp. 449-483

BibTeX  Abstract Full Text:  PDF

The Mixing Time of the Thorp Shuffle

Ben Morris

pp. 484-504

BibTeX  Abstract Full Text:  PDF

Every Monotone Graph Property Is Testable

Noga Alon and Asaf Shapira

pp. 505-522

BibTeX  Abstract Full Text:  PDF

The Round Complexity of Two-Party Random Selection

Saurabh Sanghvi and Salil Vadhan

pp. 523-550

BibTeX  Abstract Full Text:  PDF

Short PCPs with Polylog Query Complexity

Eli Ben-Sasson and Madhu Sudan

pp. 551-607

BibTeX  Abstract Full Text:  PDF

Lower-Stretch Spanning Trees

Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng

pp. 608-628

BibTeX  Abstract Full Text:  PDF

Improved Approximation Algorithms for Minimum Weight Vertex Separators

Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee

pp. 629-657

BibTeX  Abstract Full Text:  PDF

Tree-Walking Automata Do Not Recognize All Regular Languages

MikoLaj Bojańczyk and Thomas Colcombet

pp. 658-701

BibTeX  Abstract Full Text:  PDF

New and Improved Constructions of Nonmalleable Cryptographic Protocols

Rafael Pass and Alon Rosen

pp. 702-752

BibTeX  Abstract Full Text:  PDF